package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/8/15 17:30
 * @Desc:
 */
public class class03_kmp {

    public static int getIndexOf(String str,String match){
        if(match == null || match.equals("") || match.length() > str.length()){
            return -1;
        }

        char[] strChars = str.toCharArray();
        char[] mChars = match.toCharArray();

        int sLength = str.length();
        int mLength = match.length();

        int[] nextArray = getNextArray(mChars);
        int x = 0;
        int y = 0;
        while (x < sLength && y < mLength){
            if(strChars[x] == mChars[y]) {
                x++;
                y++;
            }else if(y == 0){
                //来到了开头的位置
                x++;
            }else {
                //假如当前的这个位置是12，当时最长前缀的长度是5 。那么就应该跳到前缀的下一个位置
                // 最长前缀就是[0....4]，下一个位置就是5的位置
                y = nextArray[y];
            }
        }
        return y == mLength ? x - y : -1;

    }

    public static int[] getNextArray(char[] chars){
        if(chars.length == 1){
            return new int[] {-1};
        }
        int[] next = new int[chars.length];
        next[0] = -1;
        next[1] = 0;

        int i = 2;//从位置2开始
        int cn = 0;
        while (i < next.length){
            if(next[i-1] == chars[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){//还能往前跳，找最长前缀
                cn=next[cn];
            }else {
                //跳到开头没有一个匹配的，找不到最长前缀
                next[i++] = 0;
            }
        }
        return next;

    }

    public static void main(String[] args) {
        int i = getIndexOf("qaacbtaacbs", "acbtaa");
        System.out.println(i);

        int[] ints= {1,2,3,4,5};

    }
}
